package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.TreeNode;

import java.util.Stack;

/**
 * @author zhaoyangfu - 2020/12/7 19:49
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [1, 2 * 104] 内
 * 1 <= Node.val <= 105
 * 1 <= low <= high <= 105
 * 所有 Node.val 互不相同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-of-bst
 */
public class BinarySearchTreeRangeSum {

    public static int rangeSumBST(TreeNode root, int low, int high) {
        int result = 0;
        if (root == null) return result;
        int val = root.val;

        // 这里的五个if和recursion中的三个if其实是一样的逻辑
        // 只是对相关的逻辑进行了拆分和整合
        if (val == low) {
            result += val;
            result += rangeSumBST(root.right, low, high);
        } else if (val == high) {
            result += val;
            result += rangeSumBST(root.left, low, high);
        } else if (val < low) {
            result += rangeSumBST(root.right, low, high);
        } else if (val > high) {
            result += rangeSumBST(root.left, low, high);
        } else {
            result += val;
            result += rangeSumBST(root.left, low, high);
            result += rangeSumBST(root.right, low, high);
        }

        return result;
    }

    /**
     * 方法一：深度优先搜索
     * 我们对树进行深度优先搜索，对于当前节点 node，如果 node.val 小于等于 L，那么只需要继续搜索它的右子树；如果 node.val 大于等于 R，那么只需要继续搜索它的左子树；如果 node.val 在区间 (L, R) 中，则需要搜索它的所有子树。
     * <p>
     * 我们在代码中用递归和迭代的方法分别实现了深度优先搜索。
     * <p>
     * <p>
     * <p>
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/range-sum-of-bst/solution/er-cha-sou-suo-shu-de-fan-wei-he-by-leetcode/
     * 来源：力扣（LeetCode）
     */
    public static int recursion(TreeNode root, int low, int high) {
        int result = 0;
        int val = root.val;
        if (low <= val && val <= high) {
            result += val;
        }

        if (low < val) {
            result += recursion(root.left, low, high);
        }

        if (val < high) {
            result += recursion(root.right, low, high);
        }

        return result;
    }

    public static int iteration(TreeNode root, int low, int high) {
        int result = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop != null) {
                int val = pop.val;
                if (low <= val && val <= high) {
                    result += val;
                }

                if (low < val) {
                    stack.push(pop.left);
                }

                if (val < high) {
                    stack.push(pop.right);
                }
            }
        }

        return result;
    }

}
